/**
 * 1）单链表的插入、删除、查找操作；
 * 2）链表中存储的是int类型的数据；
 */
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = new Node('head');
  }
  // 根据value查找节点
  findByValue(item) {
    let currentNode = this.head.next;
    while (currentNode !== null && currentNode.element !== item) {
      currentNode = currentNode.next;
    }
    console.log(currentNode);
    return currentNode === null ? -1 : currentNode;
  }

  // 根据index查找节点，下标从0开始
  findByIndex(index) {
    let currentNode = this.head.next;
    let pos = 0;
    while (currentNode !== null && pos !== index) {
      currentNode = currentNode.next;
      pos++;
    }
    console.log(currentNode);
    return currentNode === null ? -1 : currentNode;
  }

  // 向链表末尾追加节点
  append(newElement) {
    const newNode = new Node(newElement);
    let currentNode = this.head;
    while (currentNode.next) {
      currentNode = currentNode.next;
    }
    currentNode.next = newNode;
  }

  // 指定元素向后插入
  insert(newElement, element) {
    const currentNode = this.findByValue(element);
    if (currentNode === -1) {
      console.log('未找到插入位置');
      return;
    }
    const newNode = new Node(newElement);
    newNode.next = currentNode.next;
    currentNode.next = newNode;
  }

  // 查找前一个
  findPrev(item) {
    let currentNode = this.head;
    while (currentNode.next !== null && currentNode.next.element !== item) {
      currentNode = currentNode.next;
    }
    if (currentNode.next === null) {
      return -1;
    }
    return currentNode;
  }

  // 根据值删除
  remove(item) {
    const prevNode = this.findPrev(item);
    if (prevNode === -1) {
      console.log('未找到元素');
      return;
    }
    prevNode.next = prevNode.next.next;
  }

  // 遍历显示所有节点
  display() {
    let currentNode = this.head.next; // 忽略头指针的值
    while (currentNode !== null) {
      console.log(currentNode.element);
      currentNode = currentNode.next;
    }
  }
}
// Test
const LList = new LinkedList();
LList.append('chen');
LList.append('curry');
LList.append('sang');
LList.append('zhao'); // chen -> curry -> sang -> zhao
console.log('-------------insert item------------');
LList.insert('qian', 'chen'); // 首元素后插入
LList.insert('zhou', 'zhao'); // 尾元素后插入
LList.display(); // chen -> qian -> curry -> sang -> zhao -> zhou
console.log('-------------remove item------------');
LList.remove('curry');
LList.display(); // chen -> qian -> sang -> zhao -> zhou
console.log('-------------find by item------------');
LList.findByValue('chen');
console.log('-------------find by index------------');
LList.findByIndex(2);
console.log('-------------与头结点同值元素测试------------');
LList.insert('head', 'sang');
LList.display(); // chen -> qian -> sang -> head -> zhao -> zhou
LList.findPrev('head'); // sang
LList.remove('head');
LList.display(); // chen -> qian -> sang -> zhao -> zhou

// 冒泡排序O（n * n）
/* 
  原理，每次都是将最大的值冒泡到最前面
*/
function bubble(arr) {
  for(let i = 0; i < arr.length - 1; i ++) {
    let hasChange = false;
    for (let j = 0; j < arr.length - 1 - i; j ++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        hasChange = true;
      }
    }
    // 说明这次冒泡过程都是有序的
    if (!hasChange) {
      break;
    }
  }
  return arr;
}
// 选择排序
/* 
  有两个区间，已排序区间，未排序区间，每次都在未
  每次都在
*/

function selectSort(arr) {
  for(let i = 0; i < arr.length - 1; i ++) {
    let minIndex = i;
    for(let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    let temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}
// 插入排序
function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let temp = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j]; // 数据前移
      j--;
    }
    // 这时j+1的位置就是temp所在的位置
    arr[j + 1] = temp;
  }
  return arr;
}

var arr = [3, 4, 5, 22, 55, 1, 6];

console.log(arr);
// console.log(selectSort(arr));
// console.log(bubble(arr));


